//
// Created by zhulingfeng on 2020/3/6.
//
#include <algorithm>
#include <binary_search/binary_search.hpp>
#include "binary_search_test.hpp"
TEST_F(BinarySearchTest, BinarySearch) {
  for (int i = 0; i < sorted_vectors_.size(); ++i) {
    auto& unique_vector = unique_sorted_vectors_[i];
    auto& targets = search_targets_vectors_[i];
    for (const auto& target : targets) {
      auto index = BinarySearch(unique_vector, target);
      auto gt = std::find(unique_vector.begin(), unique_vector.end(), target);
      bool find = std::binary_search(unique_vector.begin(), unique_vector.end(),
                                     target);
      EXPECT_EQ(index >= 0, find);
      if (index < 0) {
        EXPECT_TRUE(gt == unique_vector.end());
      } else {
        EXPECT_EQ(index, gt - unique_vector.begin());
      }
    }
  }
}

TEST_F(BinarySearchTest, SearchRange) {
  for (int i = 0; i < sorted_vectors_.size(); ++i) {
    auto& vector = sorted_vectors_[i];
    auto& targets = search_targets_vectors_[i];
    for (const auto& target : targets) {
      auto res = SearchRange(vector, target);
      auto equal_range =
          std::equal_range(vector.cbegin(), vector.cend(), target);
      auto lower_bound = equal_range.first;
      auto upper_bound = equal_range.second;

      if (lower_bound == upper_bound) {
        EXPECT_EQ(res[0], -1);
        EXPECT_EQ(res[1], -1);
      } else {
        EXPECT_EQ(res[0], lower_bound - vector.cbegin());
        EXPECT_EQ(res[1], upper_bound - vector.cbegin() - 1);
      }
    }
  }
}

TEST_F(BinarySearchTest, SearchRangeWithTricks) {
  for (int i = 0; i < sorted_vectors_.size(); ++i) {
    auto& vector = sorted_vectors_[i];
    auto& targets = search_targets_vectors_[i];
    for (const auto& target : targets) {
      auto res = SearchRangeWithTricks(vector, target);
      auto equal_range =
          std::equal_range(vector.cbegin(), vector.cend(), target);
      auto lower_bound = equal_range.first;
      auto upper_bound = equal_range.second;

      if (lower_bound == upper_bound) {
        EXPECT_EQ(res[0], -1);
        EXPECT_EQ(res[1], -1);
      } else {
        EXPECT_EQ(res[0], lower_bound - vector.cbegin());
        EXPECT_EQ(res[1], upper_bound - vector.cbegin() - 1);
      }
    }
  }
}

TEST_F(BinarySearchTest, SearchRoatedArrayWithoutDuplicated) {
  for (int i = 0; i < unique_sorted_vectors_.size(); ++i) {
    auto& unique = unique_sorted_vectors_[i];
    auto rotated = unique_sorted_vectors_[i];
    auto mid = rotated.begin() + (rotated.end() - rotated.begin()) / 2;
    std::rotate(rotated.begin(), mid, rotated.end());
    auto& targets = search_targets_vectors_[i];
    for (const auto& target : targets) {
      bool found = std::binary_search(unique.begin(), unique.end(), target);
      int res = SearchRotatedArrayWithoutDuplicates(unique, target);
      if (!found) {
        EXPECT_EQ(res, -1);
      } else {
        ASSERT_GE(res, 0);
        ASSERT_LT(res, unique.size());
        auto gt = std::find(unique.begin(), unique.end(), target);
        EXPECT_EQ(unique[res], *gt);
      }
    }
  }
}
TEST_F(BinarySearchTest, SearchRoatedArrayWithoutDuplicated2) {
  for (int i = 0; i < unique_sorted_vectors_.size(); ++i) {
    auto& unique = unique_sorted_vectors_[i];
    auto rotated = unique_sorted_vectors_[i];
    auto mid = rotated.begin() + (rotated.end() - rotated.begin()) / 2;
    std::rotate(rotated.begin(), mid, rotated.end());
    auto& targets = search_targets_vectors_[i];
    for (const auto& target : targets) {
      bool found = std::binary_search(unique.begin(), unique.end(), target);
      int res = SearchRotatedArrayWithoutDuplicates2(unique, target);
      if (!found) {
        EXPECT_EQ(res, -1);
      } else {
        ASSERT_GE(res, 0);
        ASSERT_LT(res, unique.size());
        auto gt = std::find(unique.begin(), unique.end(), target);
        EXPECT_EQ(unique[res], *gt);
      }
    }
  }
}
TEST_F(BinarySearchTest, SearchRoatedArray) {
  for (int i = 0; i < unique_sorted_vectors_.size(); ++i) {
    auto& unique = unique_sorted_vectors_[i];
    auto rotated = unique_sorted_vectors_[i];
    auto mid = rotated.begin() + (rotated.end() - rotated.begin()) / 2;
    std::rotate(rotated.begin(), mid, rotated.end());
    auto& targets = search_targets_vectors_[i];
    for (const auto& target : targets) {
      bool found = std::binary_search(unique.begin(), unique.end(), target);
      int res = SearchRotatedArray(unique, target);
      if (!found) {
        EXPECT_EQ(res, -1);
      } else {
        ASSERT_GE(res, 0);
        ASSERT_LT(res, unique.size());
        auto gt = std::find(unique.begin(), unique.end(), target);
        EXPECT_EQ(unique[res], *gt);
      }
    }
  }
}
